% !TEX program = xelatex

\documentclass[UTF8,12pt]{ctexart} % 12pt 为字号大小
\usepackage{amssymb,amsfonts,amsmath,amsthm}
%\usepackage{fontspec,xltxtra,xunicode}
%\usepackage{times}
\renewcommand{\vec}[1]{\boldsymbol{#1}} % Uncomment for BOLD vectors.

%\usepackage{CJKutf8}

\usepackage{xeCJK}

\usepackage{indentfirst}
\setlength{\parindent}{2em}

\renewcommand{\baselinestretch}{1.4} % 1.4倍行距

%页边距
\usepackage[a4paper]{geometry}
\geometry{verbose,
    tmargin=2cm,% 上边距
    bmargin=2cm,% 下边距
    lmargin=2cm,% 左边距
    rmargin=2cm % 右边距
}

%图形相关
\usepackage[x11names]{xcolor} % must before tikz, x11names defines RoyalBlue3
\usepackage{graphicx}
\usepackage{pstricks,pst-plot,pst-eps}
\usepackage{subfig}
\def\pgfsysdriver{pgfsys-dvipdfmx.def} % put before tikz
\usepackage{tikz}

\usepackage[boxruled,algosection,linesnumbered]{algorithm2e}

\usepackage{listings}
\usepackage{color}

\usepackage{authblk}
\usepackage{abstract}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{
    frame=shadowbox,
    aboveskip=3mm,
    belowskip=3mm,
    showstringspaces=false,
    columns=flexible,
    basicstyle={\small\ttfamily},
    numbers=none,
    numberstyle=\tiny\color{gray},
    keywordstyle=\color{blue},
    commentstyle=\color{dkgreen},
    stringstyle=\color{mauve},
    breaklines=true,
    breakatwhitespace=true,
    tabsize=4,
    rulesepcolor=\color{red!20!green!20!blue!20},
}

%原文照排
\usepackage{verbatim}

\usepackage{url}

%习题环境
\theoremstyle{definition} 
\newtheorem{exs}{习题}

%解答环境
\ifx\proof\undefined\
\newenvironment{proof}[1][\protect\proofname]{\par
\normalfont\topsep6\p@\@plus6\p@\relax
\trivlist
\itemindent\parindent
\item[\hskip\labelsep
\scshape
#1]\ignorespaces
}{%
\endtrivlist\@endpefalse
}
\fi

\renewcommand{\proofname}{\it{解答}}

\begin{document}

\title{基于Spark的图划分算法实现}
\author[1]{李亮德}
\author[1]{王凌霄}
\author[2]{曹籽文}
\author[2]{侯诗铭}
\author[2]{路宏琳}
\author[3]{尉德利}
\affil[1]{中国科学院自动化研究所}
\affil[2]{中国科学院信息工程研究所}
\affil[3]{中国科学院大学人工智能学院}
\renewcommand\Authands{, }
% \date{} % 若不需要自动插入日期，则去掉前面的注释；{ } 中也可以自定义日期格式

\maketitle

\renewcommand{\abstractname}{}
\begin{onecolabstract}
    随着大数据时代的到来，数据的规模以前所未有的速度增长着，仅万维网的搜索引擎就可以抓取约一万亿的连接关系图。图作为一种由顶点和边构成的数据结构，能够简洁有力的表达事物之间的联系。
    对于大规模图的处理，必须进行图划分，降低分布式处理的各子图之间的耦合性，提高子图内部的连通性。
    常规的图划分算法有hash分区、谱聚类、Kernighan–Lin算法以及METIS算法。本项目基于内存分布式计算框架spark，通过裸RDD封装了图结构，设计并实现了以上几种图划分算法的分布式算法。然而图划分算法的spark分布式实现有很多值得优化地方。本项目针对Kernighan–Lin算法计算最大增益复杂度过高的缺点，本项目提出stochastic max gian和mini-partition max gain两种策略；针对谱聚类特征值分解复杂度过高，难以并行化的缺点，本项目采用了幂迭代法来进行特征值分解；针对metis算法在粗化过程中，本项目针对heavy edge match(HEM)存在的匹配点过于密集的缺点，使用了random heavy edge match(RHEM)最大匹配策略，让匹配点的分布更加均匀；
    针对metis在划分阶段容易产生不平衡划分的缺点，本文在谱聚类基础上，提出用节点的weight的$\alpha$次方对拉普拉斯矩阵矩阵归一化。本项目在spark平台下用三种数据集（一个无向图，一个有向图，一个无向带权图）探索了各种算法的图划分质量与运行时间在不同参数条件下的异同，以及算法之间的横向对比，还检验了本项目提出的各种改进算法的有效性。得出的主要结论表明：1、hash图划分效果较差，Kernighan–Lin算法对初始图划分很敏感，且只适合小图；2、RHEM最大匹配策略能有效避免多次粗化之后匹配点聚集，从而提高图划分质量；3、weight normalization能有效的缓解谱聚类对于点带权图划分不平衡的缺点；4、METIS算法在三个数据集下得到的图划分质量都比谱聚类高，但是谱聚类的运行时间比METIS算法低不少。
\end{onecolabstract}

\newpage
\tableofcontents
\newpage

\input{section/sec1_intro.tex}
\input{section/sec2_algorithm.tex}
\input{section/sec3_spark.tex}
\input{section/sec4_experiment.tex}
\input{section/sec5_conclusion.tex}
\input{section/sec6_teamwork.tex}

\end{document}
